#include <bits/stdc++.h>

using namespace std;

// 暴力方法
// 为了找规律
// 如果h==0，返回2*n的区域铺满的方法数
// 如果h==1，返回1 + 2*n的区域铺满的方法数
int f(int n, int h)
{
    if(n == 0) return h == 0 ? 1 : 0;
    if(n == 1) return 1;
    if(h == 1) return f(n - 1, 0) + f(n - 1, 1);
    return f(n - 1, 0) + f(n - 2, 0) + 2 * f(n - 2, 1);
}

// 多米诺和托米诺平铺
// 有两种形状的瓷砖，一种是2*1的多米诺形，另一种是形如"L"的托米诺形
// 两种形状都可以旋转，给定整数n，返回可以平铺2*n的面板的方法数量
// 返回对1000000007取模的值
// 测试链接 : https://leetcode.cn/problems/domino-and-tromino-tiling/

class Solution 
{
public:
    const int MOD = 1e9 + 7;

    // 动态规划 O(n)
    int numTilings1(int n) 
    {
        if(n <= 2) return n;
        if(n == 3) return 5;
        long dp[n + 1];
        dp[1] = 1, dp[2] = 2, dp[3] = 5;
        for(int i = 4; i <= n; ++i)
        {
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;
        }
        return dp[n];
    }

    // 正式方法
    // 矩阵快速幂
    // 时间复杂度O(logn)
    int numTilings2(int n) 
    {
        if(n <= 2) return n;
        if(n == 3) return 5;
        vector<vector<int>> start = {{5, 2, 1}};
        vector<vector<int>> base = {
            {2, 1, 0},
            {0, 0, 1},
            {1, 0, 0}
        };
        vector<vector<int>> ans = multiply(start, power(base, n - 3));
        return ans[0][0];
    }

	// 矩阵相乘 + 乘法取模
	// a的列数一定要等于b的行数
    vector<vector<int>> multiply(const vector<vector<int>>& a, const vector<vector<int>>& b)
    {
        int m = a.size();
        int n = b.size();
        int k = a[0].size();
        vector<vector<int>> ans(m, vector<int>(n));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                for(int c = 0; c < k; ++c)
                {
                    ans[i][j] = (ans[i][j] + (long)a[i][c] * b[c][j]) % MOD;
                }
            }
        }
        return ans;
    }

    // 矩阵快速幂
    vector<vector<int>> power(vector<vector<int>>& m, int p)
    {
        int n = m.size();
        vector<vector<int>> ans(n, vector<int>(n));
        for(int i = 0; i < n; ++i) ans[i][i] = 1;
        while(p)
        {
            if(p & 1) ans = multiply(ans, m);
            m = multiply(m, m);
            p >>= 1;
        }
        return ans;
    }
};

int main()
{
	// f(1) = 1
	// f(2) = 2
	// f(3) = 5
	// f(4) = 11
	// f(n) = 2 * f(n-1) + f(n-3)
	// 打表或者公式化简都可以发现规律，这里推荐打表找规律
    for(int i = 1; i <= 9; ++i)
    {
        printf("铺满 2 * %d 的区域方法数 : %d\n", i, f(i, 0));
    }

    return 0;
}